package 面试题33_二叉搜索树的后序遍历序列;

import org.junit.Test;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 15:45 2021/2/19
 * @Description：
 */
public class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if (postorder == null) return false;

        if (postorder.length == 0) return true;

        return verifyRercu(postorder, 0, postorder.length - 1);
    }

    boolean verifyRercu(int[] postorder, int start, int end) {
        if ((end - start) < 0) {
            return false;
        }

        if ((end - start) == 0) {
            return true;
        }

        int root = postorder[end];

        // 遍历序列，找到左右子树的分界点
        int rightStart;
        for (rightStart = start; rightStart < end; rightStart++) {
            if (postorder[rightStart] > root) {
                break;
            }
        }

        // 判断序列中后半部分是否大于根节点
        // 不是二叉搜索树的情况：比根节点大的值出现在左侧，则在比较时会发现被判定为右子树的部分出现比根节点小的值
        for (int j = rightStart; j < end; j++) {
            if (postorder[j] < root) {
                return false;
            }
        }

        boolean left = true;
        boolean right = true;

        // 递归判断左序列能够构成二叉搜索树
        if (start <= rightStart - 1) {
            left = verifyRercu(postorder, start, rightStart - 1);
        }

        // 递归判断右序列能够构成二叉搜索树
        if (rightStart <= end - 1) {
            right = verifyRercu(postorder, rightStart, end - 1);
        }

        return (left && right);
    }

    @Test
    public void test() {
        int[] postorder = {1,2,5,10,6,9,4,3};

        verifyPostorder(postorder);
    }
}
